package com.wj.algorithm.lintcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class P121 {
    class WordNode {
        private String word;
        private int degree = 0;
        private List<String> neighbors = new ArrayList<String>();
        private boolean isEnd;
        private int reachedMinLen = Integer.MAX_VALUE;
        public WordNode() {
            
        }
        public WordNode(String word) {
            super();
            this.word = word;
        }

        public String getWord() {
            return word;
        }
        public int getDegree() {
            return degree;
        }
        public List<String> getNeighbors() {
            return neighbors;
        }
        public boolean isEnd() {
            return isEnd;
        }
        public void addNeighbor(String s) {
            neighbors.add(s);
            degree ++;
        }
    }
    //判断两个字符串是否相邻，来确定是否是连通图的相邻节点
    public static boolean isNeighbor(String a, String b) {
        int diff = 0;
        for(int i = 0, len = a.length(); i < len; i ++) {
            if(a.charAt(i) != b.charAt(i)) {
                diff ++;
            }
            if(diff > 1) {
                return false;
            }
        }
        return diff == 1;
    }
    private void fillGraph(Map<String, WordNode> temp, String a, String b) {
        WordNode nodeA = temp.get(a);
        if(nodeA == null) {
            nodeA = new WordNode(a);
            temp.put(a, nodeA);
        }
        nodeA.addNeighbor(b);
        
        WordNode nodeB = temp.get(b);
        if(nodeB == null) {
            nodeB = new WordNode(b);
            temp.put(b, nodeB);
        }
        nodeB.addNeighbor(a);
    }
    
    //建立无向连通图
    private WordNode createGraph(Map<String, WordNode> temp, String start, String end, Set<String> dict) {
//        dict.add(end);
        dict.add(start);
        List<String> list = new ArrayList<String>();
        for(String s : dict) {
            list.add(s);
        }
        
        for(int i = 0, len = list.size(); i < len; i ++) {
            for(int j = i + 1; j < len; j ++) {
                String a = list.get(i);
                String b = list.get(j);
                if(isNeighbor(a, b)) {
                    fillGraph(temp, a, b);
                }
            }
        }
        
        WordNode endNode = temp.get(end);
        if(endNode == null) {
            return null;
        }
        endNode.isEnd = true;
        
      //转为有向图
        WordNode rsNode = temp.get(start);
        Set<String> isIn = new HashSet<>();
        isIn.add(start);
        List<String> nexts = rsNode.getNeighbors();
        while(nexts.size() > 0) {
            List<String> nextsTemp = new ArrayList<String>();
            for(String i : nexts) {
                isIn.add(i);
            }
            for(String i : nexts) {
                WordNode thisNode = temp.get(i);
                if(thisNode != null) {
                    List<String> subSub = thisNode.getNeighbors();
                    thisNode.neighbors = new ArrayList<String>(0);
                    for(String j : subSub) {
                        if(isIn.contains(j)) {
                            continue;
                        }
                        thisNode.addNeighbor(j);

                        if(!nextsTemp.contains(j)) {
                            nextsTemp.add(j);
                        }
                    }
                }
            }
            
            nexts = nextsTemp;
        }
        
        return temp.get(start);
    }
    
    private List<String> copyAndAdd(List<String> list, String add) {
        List<String> rs = new ArrayList<String>();
        for(String s : list) {
            rs.add(s);
        }
        if(add != null) {
            rs.add(add);
        }
        return rs;
    }
    
    private List<String> remove(List<String> src, List<String> moved) {
        List<String> rs = new ArrayList<String>();
        for(String s : src) {
            if(moved.contains(s)) {
                continue;
            }
            rs.add(s);
        }
        return rs;
    }
    
    private List<List<String>> find(List<String> preList, List<String> nexts, Map<String, WordNode> temp, String end) {
        List<List<String>> resultList = new ArrayList<List<String>>();

        int preSize = preList.size();
        int reachedLen = preSize + 1;
        //先检查是否有结尾，有结尾的直接返回
        for(String next : nexts) {
            if(next.equals(end)) {
                temp.get(next).reachedMinLen = preSize;
                resultList = new ArrayList<List<String>>();
                resultList.add(copyAndAdd(preList, next));
                return resultList;
            }
        }
        
        //结尾相邻的
        for(String next : nexts) {
            if(isNeighbor(next, end)) {
                temp.get(next).reachedMinLen = reachedLen;
                List<String> finalList = copyAndAdd(preList, next);
                finalList.add(end);
                resultList.add(finalList);
            }
        }
        if(resultList.size() > 0) {
            return resultList;
        }
        
        
        //其他
        List<String> dulp = copyAndAdd(preList, null);
        dulp.addAll(nexts);
        for(String next : nexts) {
            WordNode nextNode = temp.get(next);
            if(nextNode == null || (!nextNode.isEnd && nextNode.degree <= 1)) {
                continue;
            }
            
            //当前到达这个节点，长度超过之前，则直接丢弃
            if(reachedLen > nextNode.reachedMinLen) {
                continue;
            }
            nextNode.reachedMinLen = reachedLen;
            //clone一份邻居节点列表
            List<String> newNeighbors = remove(nextNode.getNeighbors(), dulp);
            if(newNeighbors.size() <= 0) {
                continue;
            }
            List<String> subPrev = copyAndAdd(preList, next);
            List<List<String>> tempResult = find(subPrev, newNeighbors, temp, end);
            if(tempResult != null && tempResult.size() > 0) {
                for(List<String> subTempList : tempResult) {
                    if(subTempList.size() > 0) {
                        resultList.add(subTempList);
                    }
                }
            }
        }
        
        return resultList;
    }

    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> resultList = new ArrayList<List<String>>();
        
        //节点保存
        Map<String, WordNode> temp = new HashMap<String, WordNode>();
        //开始节点
        WordNode graph = createGraph(temp, start, end, dict);
        if(graph == null) {
            return resultList;
        }
        if(graph.degree <= 0) {
            return resultList;
        }
        List<String> startList = new ArrayList<String>();
        startList.add(start);
        
        resultList = find(startList, graph.getNeighbors(), temp, end);
        
        int minSize = Integer.MAX_VALUE;
        List<List<String>> bestResultList = new ArrayList<List<String>>();
        for(List<String> subTempList : resultList) {
            int tempSize = subTempList.size();
            if(tempSize > 0 && tempSize <= minSize) {
                if(tempSize < minSize) {
                    bestResultList.clear();
                }
                minSize = tempSize;
                bestResultList.add(subTempList);
            }
        }
        if(minSize < Integer.MAX_VALUE) {
            return bestResultList;
        }

        return resultList;
    }
    
    public static void main(String[] args) {
        P121 p = new P121();
        String[] temp = new String[]{
                
                ////"qa", "sq"
//                "si","go","se","cm","so","ph","mt","db","mb","sb","kr","ln",
//                "tm","le","av","sm","ar","ci","ca","br","ti","ba","to","ra","fa","yo","ow","sn",
//                "ya","cr","po","fe","ho","ma","re","or","rn","au","ur","rh","sr","tc","lt","lo",
//                "as","fr","nb","yb","if","pb","ge","th","pm","rb","sh","co","ga","li","ha","hz",
//                "no","bi","di","hi","qa","pi","os","uh","wm","an","me","mo","na","la","st","er",
//                "sc","ne","mn","mi","am","ex","pt","io","be","fm","ta","tb","ni","mr","pa","he",
//                "lr","sq","ye"
                
//                "hot","cog","dog","tot","hog","hop","pot","dot"
                
                ////"cet", "ism"
                "kid","tag","pup","ail","tun","woo","erg","luz","brr","gay","sip","kay","per","val","mes","ohs","now","boa","cet","pal","bar","die","war","hay","eco","pub","lob","rue","fry","lit","rex","jan","cot","bid","ali","pay","col","gum","ger","row","won","dan","rum","fad","tut","sag","yip","sui","ark","has","zip","fez","own","ump","dis","ads","max","jaw","out","btu","ana","gap","cry","led","abe","box","ore","pig","fie","toy","fat","cal","lie","noh","sew","ono","tam","flu","mgm","ply","awe","pry","tit","tie","yet","too","tax","jim","san","pan","map","ski","ova","wed","non","wac","nut","why","bye","lye","oct","old","fin","feb","chi","sap","owl","log","tod","dot","bow","fob","for","joe","ivy","fan","age","fax","hip","jib","mel","hus","sob","ifs","tab","ara","dab","jag","jar","arm","lot","tom","sax","tex","yum","pei","wen","wry","ire","irk","far","mew","wit","doe","gas","rte","ian","pot","ask","wag","hag","amy","nag","ron","soy","gin","don","tug","fay","vic","boo","nam","ave","buy","sop","but","orb","fen","paw","his","sub","bob","yea","oft","inn","rod","yam","pew","web","hod","hun","gyp","wei","wis","rob","gad","pie","mon","dog","bib","rub","ere","dig","era","cat","fox","bee","mod","day","apr","vie","nev","jam","pam","new","aye","ani","and","ibm","yap","can","pyx","tar","kin","fog","hum","pip","cup","dye","lyx","jog","nun","par","wan","fey","bus","oak","bad","ats","set","qom","vat","eat","pus","rev","axe","ion","six","ila","lao","mom","mas","pro","few","opt","poe","art","ash","oar","cap","lop","may","shy","rid","bat","sum","rim","fee","bmw","sky","maj","hue","thy","ava","rap","den","fla","auk","cox","ibo","hey","saw","vim","sec","ltd","you","its","tat","dew","eva","tog","ram","let","see","zit","maw","nix","ate","gig","rep","owe","ind","hog","eve","sam","zoo","any","dow","cod","bed","vet","ham","sis","hex","via","fir","nod","mao","aug","mum","hoe","bah","hal","keg","hew","zed","tow","gog","ass","dem","who","bet","gos","son","ear","spy","kit","boy","due","sen","oaf","mix","hep","fur","ada","bin","nil","mia","ewe","hit","fix","sad","rib","eye","hop","haw","wax","mid","tad","ken","wad","rye","pap","bog","gut","ito","woe","our","ado","sin","mad","ray","hon","roy","dip","hen","iva","lug","asp","hui","yak","bay","poi","yep","bun","try","lad","elm","nat","wyo","gym","dug","toe","dee","wig","sly","rip","geo","cog","pas","zen","odd","nan","lay","pod","fit","hem","joy","bum","rio","yon","dec","leg","put","sue","dim","pet","yaw","nub","bit","bur","sid","sun","oil","red","doc","moe","caw","eel","dix","cub","end","gem","off","yew","hug","pop","tub","sgt","lid","pun","ton","sol","din","yup","jab","pea","bug","gag","mil","jig","hub","low","did","tin","get","gte","sox","lei","mig","fig","lon","use","ban","flo","nov","jut","bag","mir","sty","lap","two","ins","con","ant","net","tux","ode","stu","mug","cad","nap","gun","fop","tot","sow","sal","sic","ted","wot","del","imp","cob","way","ann","tan","mci","job","wet","ism","err","him","all","pad","hah","hie","aim","ike","jed","ego","mac","baa","min","com","ill","was","cab","ago","ina","big","ilk","gal","tap","duh","ola","ran","lab","top","gob","hot","ora","tia","kip","han","met","hut","she","sac","fed","goo","tee","ell","not","act","gil","rut","ala","ape","rig","cid","god","duo","lin","aid","gel","awl","lag","elf","liz","ref","aha","fib","oho","tho","her","nor","ace","adz","fun","ned","coo","win","tao","coy","van","man","pit","guy","foe","hid","mai","sup","jay","hob","mow","jot","are","pol","arc","lax","aft","alb","len","air","pug","pox","vow","got","meg","zoe","amp","ale","bud","gee","pin","dun","pat","ten","mob"
        };
        Set<String> dict = new HashSet<>();
        for(String s : temp) {
            dict.add(s);
        }
        
//        dict.clear();
//        dict.add("a");
//        dict.add("b");
//        dict.add("c");
        
        long begin = System.currentTimeMillis();
        List<List<String>> rs = p.findLadders("cet", "ism", dict);
        
        for(List<String> tempList : rs) {
            System.out.println(tempList);
        }
        System.out.println("cost : " + (System.currentTimeMillis() - begin));
    }
}
